import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-14
 */
public class leetcode_234 {
    public static void main(String[] args) {
        //ListNode list = new ListNode(1, new ListNode(2, new ListNode(2,new ListNode(2, new ListNode(1)))));
        ListNode list = new ListNode(1, new ListNode(2));
        System.out.println(isPalindrome1(list));
    }

    public boolean isPalindrome(ListNode head) {
        ListNode headNode = new ListNode(0, head);
        if (head == null) return false;
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
        }
        while (head.next != null) {
            ListNode tmp = head.next;
            head.next = tmp.next;
            tmp.next = headNode.next;
            headNode.next = tmp;
        }
        int index = 0;
        while (headNode.next != null) {
            if (headNode.next.val != list.get(index)) return false;
            index++;
            headNode = headNode.next;
        }
        return true;
    }

    public static boolean isPalindrome1(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode headNode = new ListNode(0, head);
        ListNode left = headNode;
        ListNode right = headNode;
        //注意快慢指针对奇偶的处理方式
        while (right != null && right.next != null) {
            left = left.next;
            right = right.next.next;
        }
        ListNode currentNode = left.next;
        while (currentNode!=null&&currentNode.next!= null) {
            ListNode tmp = currentNode.next;
            currentNode.next= tmp.next;
            tmp.next=left.next;
            left.next = tmp;
        }
        ListNode first = head;
        ListNode last = left.next;
        while(first!=left.next&&first!=null&&last!=null){
           if(first.val!=last.val)return false;
           first = first.next;
           last =last.next;
        }
        return true;
    }

//    public static boolean isPalindrome2(ListNode head) {
//        if (head == null || head.next == null) return true;
//        ListNode slow = head;
//        ListNode fast = head;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
